package org.yimon.tool.algo.leetcode;

/**
 * @Author yimon.gao
 * @Description 寻找重复数
 * @Date 2024/9/3 上午11:27
 */
public class LeetCode_287_FindDuplicate {

    public static void main(String[] args) {
        System.out.println(LeetCode_287_FindDuplicate.findDuplicate(new int[]{1, 3, 4, 2, 2}));
    }

    public static int findDuplicate(int[] nums) {
        //特殊情况判断，一定没有重复数的情况
        if (nums == null || nums.length < 2) {
            return -1;
        }
        //我们可以先对nums的数值-1，这样我们就可以得到一个数组的索引位置
        //然后我们把这个索引位置的数值变成一个负数
        //遇到重复数的情况下：我们可以判断索引位置如果为负数，则说明当前索引位置的数是重复数
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            int index = Math.abs(num) - 1;//这里需要注意，num需要取绝对值，因为可能被变更成负数了
            //获取索引位置对应的数
            int math = nums[index];
            if (math < 0) {//表示当前数字已经被修改过一次，重复了
                return index + 1;
            } else {
                nums[index] = -math;//将当前的数变成负数
            }
        }
        return -1;
    }
}
